package com.guqj.basis.datastruct.doublelist;

public class LinkList<T> {

	private Node<T> head;
	private Node<T> tail;
	private int size;

	private static class Node<T> {
		T element;
		Node<T> prev;
		Node<T> next;

		public Node(T element, Node<T> prev, Node<T> next) {
			this.element = element;
			this.prev = prev;
			this.next = next;
		}
	}

	public void add(T e) {
		Node<T> t = tail;
		final Node<T> n = new Node<>(e, t, null);
		tail = n;
		if (t == null) {
			head = n;
		} else {
			t.next = n;
		}
		size++;
	}

	public void addFirst(T e) {
		final Node<T> x = head;
		final Node<T> n = new Node<>(e, null, x);
		head = n;
		if (x == null) {
			tail = n;
		} else {
			x.prev = n;
		}
		size++;
	}

	public void addLast(T e) {
		add(e);
	}

	public void add(int index, T e) {
		if (!checkPosition(index)) {
			throw new IndexOutOfBoundsException();
		}
		if (index == 0) {
			addFirst(e);
		} else if (index == size) {
			addLast(e);
		} else {
			Node<T> next = node(index);
			Node<T> prev = next.prev;
			final Node<T> newNode = new Node<T>(e, prev, next);
			prev.next = newNode;
			next.prev = newNode;
			size++;
		}
	}

	public boolean remove(int index) {
		if (!checkPosition(index)) {
			throw new IndexOutOfBoundsException();
		}
		return remove(node(index));
	}

	private boolean remove(Node<T> node) {
		Node<T> pred = node.prev;
		Node<T> next = node.next;
		if (pred == null) {
			head = next;
		} else {
			pred.next = next;
			node.prev = null;
		}

		if (next == null) {
			tail = pred;
		} else {
			next.prev = pred;
			node.next = null;
		}
		node.element = null;
		size--;
		return true;
	}

	public boolean remove(T e) {
		if (e == null) {
			return false;
		}
		for (Node<T> x = head; x != null; x = x.next) {
			if (e.equals(x.element)) {
				return remove(x);
			}
		}
		return false;
	}

	private boolean checkPosition(int index) {
		return index >= 0 && index < size;
	}

	Node<T> node(int index) {
		if (index < (size >> 1)) { // 二分查找
			Node<T> x = head;
			for (int i = 0; i < index; i++) {
				x = x.next;
			}
			return x;
		} else {
			Node<T> x = tail;
			for (int i = size - 1; i > index; i--) {
				x = x.prev;
			}
			return x;
		}
	}

	public T get(int index) {
		if (!checkPosition(index)) {
			throw new IndexOutOfBoundsException();
		}
		Node<T> n = node(index);
		return n.element;
	}

	public int size() {
		return size;
	}

	public static void main(String[] args) {
		LinkList<String> list = new LinkList<>();
		list.add("JAVA");
		list.add("PHP");
		list.addFirst("Python");
		list.add(1, "Ruby");
		int size = list.size();
		for (int i = 0; i < size; i++) {
			System.out.print(list.get(i) + " ");
		}
		list.remove("JAVA");
		System.out.println();
		size = list.size();
		for (int i = 0; i < size; i++) {
			System.out.print(list.get(i) + " ");
		}
		System.out.println();
		System.out.println(list.get(size - 1));
	}
}
